package Leetcode.Stack;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/4/13 17:00
 * @Description:
 * 链表中的下一个更大节点
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给定一个长度为 n 的链表 head
 *
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
 *
 * 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [2,1,5]
 * 输出：[5,5,0]
 * 示例 2：
 *
 *
 *
 * 输入：head = [2,7,4,3,5]
 * 输出：[7,0,5,5,0]
 *
 *
 * 提示：
 *
 * 链表中节点数为 n
 * 1 <= n <= 104
 * 1 <= Node.val <= 109
 */

public class nextLargerNodes {
    public static void main(String[] args) {
        int[] nums = {2, 1, 5};
        System.out.println(Arrays.toString(get(nums)));
    }
    /**
     *暴力
     *
     * @param head
     * @return
     */
    public int[] nextLargerNodes1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            ListNode temp = head;
            while (temp != null) {
                if (head.val < temp.val) {
                    list.add(temp.val);
                    break;
                }else{
                    temp = temp.next;
                    if (temp == null) {
                        list.add(0);
                    }
                }
            }
            head = head.next;
        }
        int size = list.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    //链表转数组在找
    public int[] nextLargerNodes2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int size = list.size();
        int[] temp = new int[size];
        for (int i = 0; i < size; i++) {
            temp[i] = list.get(i);
        }
        int[] ans = get(temp);
        return ans;
    }

    private static int[] get(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int preIndex = stack.pop();
                ans[preIndex] = nums[i];
            }
            stack.push(i);
        }
        return ans;
    }
    private int[] ans;
    private final Deque<Integer> stack = new ArrayDeque<>(); // 单调栈（节点值）

    public int[] nextLargerNodes(ListNode head) {
        f(head, 0);
        return ans;
    }

    private void f(ListNode node, int i) {
        if (node == null) {
            ans = new int[i]; // i 就是链表长度
            return;
        }
        f(node.next, i + 1);
        while (!stack.isEmpty() && stack.peek() <= node.val){
            stack.pop(); // 弹出无用数据
        }
        if (!stack.isEmpty()){
            ans[i] = stack.peek(); // 栈顶就是第 i 个节点的下一个更大元素
        }
        stack.push(node.val);
    }

}
